#ifndef __HASHMAP_H_
#define __HASHMAP_H_

#include <string>
#include <iostream>

template <typename T>
class HashMap
{
public:
    HashMap(const int &size);
    void Insert(const std::string &key, const T &value);
    void Remove(const std::string &key);
    T *GetByKey(const std::string &key);
    T &operator[](const std::string &key);
    // void showByGoup();

    template <typename U>
    friend std::ostream &operator<<(std::ostream &os, const HashMap<U> &hash);

private:
    struct Node
    {
        Node(const std::string &key, const T &value) : key(key), value(value), next(nullptr) {}
        std::string key;
        T value;
        Node *next;
    };
    Node **array;
    const int size;
    int Hash(const std::string &key);
};

template <typename T>
HashMap<T>::HashMap(const int &size) : size(size)
{
    array = new Node *[size];
    for (int i = 0; i < size; i++)
    {
        array[i] = nullptr;
    }
}

template <typename T>
void HashMap<T>::Insert(const std::string &key, const T &value)
{
    Node *node = new Node(key, value); // 构建一个结点
    // 计算哈希值
    int index = Hash(key);
    // 头插
    node->next = array[index];
    array[index] = node;
}

template <typename T>
void HashMap<T>::Remove(const std::string &key)  // 分两种情况，要么是当前的，要么后面存在链表
{
    Node *node = array[Hash(key)];
    if (node == nullptr)
        return;
    if (node->key == key)  
    {
        array[Hash(key)] = node->next;
        delete node;
        return;
    }
    else // 是这个，但是不是当前的，说明后面有链表
    {
        Node *travelPoint = node; // 删除的是下一个，所以需要从node开始
        while (travelPoint->next != nullptr)
        {
            if (travelPoint->next->key == key)
            {
                Node *freeNode = travelPoint->next;
                travelPoint->next = freeNode->next;
                delete freeNode;
            }
            travelPoint = travelPoint->next;
        }
    }
}

template <typename T>
T *HashMap<T>::GetByKey(const std::string &key)
{
    Node *node = array[Hash(key)]; 
    while (node != nullptr)      
    {
        if (node->key == key)
        {
            return &node->value;
        }
        node = node->next;
    }
    return nullptr;
}

template <typename T>
T &HashMap<T>::operator[](const std::string &key)
{
    T *data = GetByKey(key);
    // 存在就返回
    if (data)
        return *data;
    // 不存在就创建
    else
    {
        Insert(key, T()); 
        return *GetByKey(key);
    }
}

template <typename T>
std::ostream &operator<<(std::ostream &os, const HashMap<T> &hash)
{
    for (int i = 0; i < hash.size; i++)
    {
        typename HashMap<T>::Node *travelPoint = hash.array[i];
        while (travelPoint != nullptr)
        {
            std::cout << "hash值:" << i << " "
                      << "key:" << travelPoint->key << " "
                      << "value:" << travelPoint->value << " ";
            travelPoint = travelPoint->next;
            std::cout << std::endl;
        }
    }
    return os;
}

template <typename T>
int HashMap<T>::Hash(const std::string &key)
{
    int hash = 0;
    for (int i = 0; i < key.size(); i++)
    {
        hash = (hash * 31 + key[i]) % size;
    }
    return hash;
}



#endif
